package leetcode.median;

import leetcode.base.TreeNode;

import java.util.HashMap;

/**
 * ClassName: $105_BuildTree
 * Description: 从前序与中序遍历序列构造二叉树
 * date: 2021-12-01 22:43
 *
 * @author liyifan
 */
public class $105_BuildTree {
    HashMap<Integer, Integer> indexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0;i < inorder.length;i++) {
            indexMap.put(inorder[i], i);
        }
        return recur(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    public TreeNode recur(int[] pre, int[] in, int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right || in_left > in_right)
            return null;
        // 构造根节点
        int root_val = pre[pre_left];
        TreeNode root = new TreeNode(root_val);
        // 在中序遍历中找到根节点的位置
//        int root_index = -1;
//        for (int i = in_left;i <= in_right;i++) {
//            if (in[i] == root_val) {
//                root_index = i;
//                break;
//            }
//        }
        int root_index = indexMap.get(root_val);
        int leftSize = root_index - in_left;
        root.left = recur(pre, in, pre_left + 1, pre_left + leftSize, in_left, root_index - 1);
        root.right = recur(pre, in, pre_left + leftSize + 1, pre_right, root_index + 1, in_right);
        return root;
    }
}
